Bà gặp nhà soạn nhạc và nhạc trưởng Leonard Bernstein trong một bữa tiệc được tổ chức bởi Arrau vào năm 1946. Cuối cùng, bà choán lấy tâm hồn của Bernstein. Tuy nhiên, điều đó đã dừng lại sau một vài tháng. Trong những năm tiếp theo, Felicia rơi vào cuộc tình lãng mạn với diễn viên của Hollywood và Broadway mang tên Richard Hart. Sau cái chết của Hart vào tháng 1 năm 1951, bà kết hôn với Bernstein vào ngày 10 tháng 9 cùng năm. Bà đã cải sang Do Thái giáo khi kết hôn. Xu hướng đồng tính luyến ái của Bernstein đã trở nên nổi bật. Người hợp tác với ông trong tác phẩm West Side Story cũng gọi ông là một "người đàn ông đồng tính". Điều này đã dẫn đến ý rằng ông quyết định kết hôn để dập tắt những tin đồn về đời tư của ông và để duy trì một vị trí chỉ huy âm nhạc lớn, sau khi nhận được một lời khuyên của người hướng dẫn ông Dimitri Mitropoulos, người đã làm cho ông hiểu được về sự tự nhiên bảo tồn của dàn nhạc giao hưởng. Felicia và Bernstein có ba người con:

• Jamie Bernstein (sinh ngày 8 tháng 9 năm 1952), lớn lên trở thành một diễn viên, đạo diễn và nhà viết kịch bản
• Alexander Bernstein (sinh ngày 7 tháng 7 năm 1955), trở thành một diễn viên và một người phối nhạc
• Nina Bernstein (sinh ngày 28 tháng 2 năm 1962

Felicia và Bernstein ban đầu có một cuộc sống hôn nhân hạnh phúc ban đầu và không có ý kiến nào chỉ ra rằng họ không yêu nhau. Tuy nhiên, theo như các báo cáo, Bernstein có những hành động ngoại tình với những chàng trai trẻ và những sự cố này đến tai Felicia. Bạn của Bernstein là Shirley Rhoades Perle đã từng nói một lần rằng "ông đã yêu cầu các chàng trai về mặt tình dục và các cô gái về mặt tình cảm". Có một bức thư được viết bởi Felicia cho Bernstein khi biết xu hướng đồng tính luyến ái, được tìm thấy trong cuốn sách được xuất bản vào năm 2013 có tên The Leonard Bernstein Letters. Trong bức thư đó, bà thừa nhận Bernstein là một người đàn ông đồng tính và có lẽ sẽ không thay đổi được điều đó. Bà cũng nói rằng bà sẵn sàng chấp nhận con người ông và viết sau đó rằng cuộc hôn nhân của họ sẽ được dựa trên sự tôn trọng lẫn nhau và sự vị tha chứ không phải bằng cảm xúc.

Vào năm 1976, cuộc hôn nhân của Felicia gặp vấn đề bởi vì Bernstein đã rời khỏi bà để tới nhà âm nhạc học Tom Cothran. Điều này xảy ra sau khi Bernstein quyết định sẽ không thể giấu được tình trạng đồng tính luyến ái của ông lâu hơn được nữa. Tuy nhiên, ông trở lại vợ mình sau khi bà được chẩn đoán là bị ung thư phổi vào năm 1977. Bernstein đã chăm sóc bà cho đến khi bà gục ngã trước bệnh tật vào ngày 16 tháng 6 năm 1978 tại East Hampton, New York.